package demo5;

import java.util.*;

class Solution {
    public static List<String> topKFrequent(String[] words, int k) {
        //遍历字符串数组  统计每个单词出现的频率
        Map<String,Integer> map = new HashMap<>();
        for (String str : words) {
            if (!map.containsKey(str)) {
                map.put(str,1);
            } else {
                map.put(str,map.get(str)+1);
            }
        }

        //2.建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //3. 将前k个元素放到小根堆中  并且比较其余剩下的
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    //频率相同的情况
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }

        }
        //4. 此时小根堆当中已经有了结果
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}